import numpy as np
import queue


# 先进先出


def FIFO(page_requests, num_frames):
    # 初始化页面队列和页面计数器
    page_queue = queue.Queue()
    page_faults = 0  # 置换次数
    g_page_requests = page_requests
    for page in g_page_requests:  # 依次请求页面
        print("页面队列", end='')
        t = list(page_queue.queue)
        print(t)
        if page in list(t):  # 如果页面已经在队列中，不需要进行任何操作
            pass
        elif page_queue.qsize() < num_frames:  # 如果页面不在队列中, 且队列未满，将页面添加到队列末尾
            page_queue.put(page)
        else:  # 如果页面队列已满，则移除最先到来的
            page_queue.get()
            page_queue.put(page)
            page_faults = page_faults + 1  # 置换次数
        page_requests = page_requests[1:]  # 删除需求队列中的第一个
    print("请求队列:", end='')
    print(page_requests)
    print("页面队列", end='')
    t = list(page_queue.queue)
    print(t)
    return page_faults


def LRU(page_requests, num_frames):
    # 初始化页面队列和页面计数器
    page_queue = []
    page_faults = 0
    page_count = []
    g_page_requests = page_requests
    for page in g_page_requests:  # 依次请求页面
        try:
            print("请求队列:", end='')
            print(page_requests)
            print("当前页面队列", end='')
            print(page_queue)
            print("页面队列的计时器", end='')
            print(page_count)

            if page in page_queue:  # 如果页面已经在队列中，刷新计时器
                t = page_queue.index(page)  # 找出索引
                page_count[t] = 0  # 刷新

            elif len(page_queue) < num_frames:  # 如果页面不在队列中, 且队列未满，将页面添加到队列末尾
                page_queue.append(page)
                page_count.append(0)  # 开始记录
            # 如果页面队列已满，则找出最近最久未使用
            else:
                t = page_count.index(max(page_count))
                page_count[t] = 0
                page_queue[t] = page
                page_faults += 1
        finally:
            page_requests = page_requests[1:]
            page_count = [x + 1 for x in page_count]  # 计数器加一
    print("请求队列:", end='')
    print(page_requests)
    print("当前页面队列", end='')
    print(page_queue)
    print("页面队列的计时器", end='')
    print(page_count)

    return page_faults


# 获得目标队列,默认20
def get_queue(num=20):
    queue_t = np.random.randint(1, 10, size=num)  # 数字范围1-10
    print(queue_t)
    return queue_t


if __name__ == '__main__':
    page_requests = get_queue()
    num_frames = 3  # 物理块数为3, 固定值

    page_faults = FIFO(page_requests, num_frames)
    print("总共需要进行 %d 次页面置换" % page_faults)
